import java.util.HashMap;

/**
 * The type Radix tree test.
 */
class RadixTreeTest {
    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        RadixTree tree = new RadixTree();
        tree.insert("test");
//        tree.insert("water");
        tree.insert("slow");
        tree.insert("slower");
//        tree.insert("team");
//        tree.insert("tester");
//        tree.insert("t");
//        tree.insert("toast");

        System.out.println("对tester的搜索结果为：" + tree.search("tester"));
        tree.printAllWords();

        tree.delete("slow");

        System.out.println("对te的搜索结果为：" + tree.search("te"));
        tree.printAllWords();
    }
}

/**
 * The type Radix tree.
 */
public class RadixTree {
    private static final int NO_MISMATCH = -1;
    private Node root;

    /**
     * Instantiates a new Radix tree.
     */
    public RadixTree() {
        root = new Node(false);
    }

    /**
     * Insert.
     *
     * @param word the word
     */
    public void insert(String word) {
        Node current = root;
        int currIndex = 0;


        while (currIndex < word.length()) {
            char transitionChar = word.charAt(currIndex);
            Edge currentEdge = current.getTransition(transitionChar);
            // 更新后缀
            String currStr = word.substring(currIndex);

            // 如果待插入的边和已有边无共同前缀，则新建一条边
            if (currentEdge == null) {
                current.edges.put(transitionChar, new Edge(currStr));
                break;
            }

            // 如果待插入的边和已有边有共同前缀，则需要把共同前缀分割出来作为一条新边，不同的部分作为新增节点的两条边
            int splitIndex = getFirstMismatchLetter(currStr, currentEdge.label);
            if (splitIndex == NO_MISMATCH) {
                // 找不到不匹配的索引，则说明是类似slow,slower这种整个词都是相同前缀的情况
                if (currStr.length() == currentEdge.label.length()) {
                    currentEdge.next.isLeaf = true;
                    break;
                } else if (currStr.length() < currentEdge.label.length()) {
                    //The leftover word is a prefix to the edge string, so split
                    String suffix = currentEdge.label.substring(currStr.length());
                    currentEdge.label = currStr;
                    Node newNext = new Node(true);
                    Node afterNewNext = currentEdge.next;
                    currentEdge.next = newNext;
                    newNext.addEdge(suffix, afterNewNext);
                    break;
                } else { //currStr.length() > currentEdge.label.length()
                    //There is leftover string after a perfect match
                    splitIndex = currentEdge.label.length();
                }
            } else {
                //The leftover string and edge string differed, so split at point
                String suffix = currentEdge.label.substring(splitIndex);
                currentEdge.label = currentEdge.label.substring(0, splitIndex);
                Node prevNext = currentEdge.next;
                currentEdge.next = new Node(false);
                currentEdge.next.addEdge(suffix, prevNext);
            }

            // 遍历基数树
            current = currentEdge.next;
            currIndex += splitIndex;
        }
    }

    /**
     * Search boolean.
     *
     * @param word the word
     * @return the boolean
     */
    public boolean search(String word) {
        Node current = root;
        int currIndex = 0;
        while (currIndex < word.length()) {
            char transitionChar = word.charAt(currIndex);
            Edge edge = current.getTransition(transitionChar);
            if (edge == null) {
                return false;
            }

            String currSubstring = word.substring(currIndex);
            if (!currSubstring.startsWith(edge.label)) {
                return false;
            }
            currIndex += edge.label.length();
            current = edge.next;
        }

        return current.isLeaf;
    }

    /**
     * Delete.
     *
     * @param word the word
     */
    public void delete(String word) {
        System.out.format("尝试删除值为%s的节点...\n", word);
        root = delete(root, word);
    }

    private Node delete(Node current, String word) {
        if (word.isEmpty()) {
            //Has no other edges,
            if (current.edges.isEmpty() && current != root) {
                return null;
            }
            current.isLeaf = false;
            return current;
        }

        char transitionChar = word.charAt(0);
        Edge edge = current.getTransition(transitionChar);
        // 不存在删除目标值时直接返回
        if (edge == null || !word.startsWith(edge.label)) {
            return current;
        }

        Node deleted = delete(edge.next, word.substring(edge.label.length()));
        if (deleted == null) {
            current.edges.remove(transitionChar);
            if (current.totalEdges() == 0 && !current.isLeaf && current != root) {
                return null;
            }
        } else if (deleted.totalEdges() == 1 && !deleted.isLeaf) {
            current.edges.remove(transitionChar);
            for (Edge afterDeleted : deleted.edges.values()) {
                current.addEdge(edge.label + afterDeleted.label, afterDeleted.next);
            }
        }
        return current;
    }

    private int getFirstMismatchLetter(String word, String edgeWord) {
        // 查找第一个不匹配的字符索引
        int LENGTH = Math.min(word.length(), edgeWord.length());
        for (int i = 1; i < LENGTH; i++) {
            if (word.charAt(i) != edgeWord.charAt(i)) {
                return i;
            }
        }
        return NO_MISMATCH;
    }

    /**
     * Print all words.
     */
    public void printAllWords() {
        System.out.println("----基数树节点值如下：----");
        printAllWords(root, "");
        System.out.println("----------------------");
    }

    private void printAllWords(Node current, String result) {
        if (current.isLeaf) {
            System.out.print(result+",");
        }

        int cnt = 0;
        for (Edge edge : current.edges.values()) {
            printAllWords(edge.next, result + edge.label);
            cnt++;
            if(current==root && cnt==current.edges.size()) System.out.println();
        }

    }


    // 每个节点都可以有边，并且有一个标志来表明它是否是一个单词的结束
    private class Node {
        private boolean isLeaf;
        private HashMap<Character, Edge> edges;

        /**
         * Instantiates a new Node.
         *
         * @param isLeaf the is leaf
         */
        public Node(boolean isLeaf) {
            this.isLeaf = isLeaf;
            edges = new HashMap<>();
        }

        /**
         * Gets transition.
         *
         * @param transitionChar the transition char
         * @return the transition
         */
        public Edge getTransition(char transitionChar) {
            return edges.get(transitionChar);
        }

        /**
         * Add edge.
         *
         * @param label the label
         * @param next  the next
         */
        public void addEdge(String label, Node next) {
            edges.put(label.charAt(0), new Edge(label, next));
        }

        /**
         * Total edges int.
         *
         * @return the int
         */
        public int totalEdges() {
            return edges.size();
        }
    }

    // 每条边都有一串字符和它通向的一个节点
    private class Edge {
        private String label;
        private Node next;

        /**
         * Instantiates a new Edge.
         *
         * @param label the label
         */
        public Edge(String label) {
            this(label, new Node(true));
        }

        /**
         * Instantiates a new Edge.
         *
         * @param label the label
         * @param next  the next
         */
        public Edge(String label, Node next) {
            this.label = label;
            this.next = next;
        }
    }
}
